package com.xyhuo.leetcode.december;

/**
 * 寻找峰值
 * https://leetcode.cn/problems/find-peak-element/
 *
 * @time 2023/12/18
 */
public class FindPeakElement {

//    public static void main(String[] args) {
//        FindPeakElement fpe = new FindPeakElement();
////        int[] nums = {1, 2, 1, 3, 5, 6, 4};
////        int[] nums = {2, 1};
////        int[] nums = {1, 2, 3};
//        int[] nums = {1, 2, 3, 4, 3};
//        int peakElement = fpe.findPeakElement(nums);
//        System.out.println(peakElement);
//    }

    public int findPeakElement(int[] nums) {
        int len = nums.length;
        this.ans = nums[len - 1] > nums[0] ? len - 1 : 0;
        findPeak(nums, 0, len - 1);
        return ans;
    }

    private int ans;

    private boolean findAns = false;

    private void findPeak(int[] nums, int left, int right) {
        if (left >= right || findAns) {
            return;
        }

        int middle = (left + right) / 2;
        if (nums[middle] > nums[left] && nums[middle] > nums[right]) {
            while (middle + 1 < nums.length && nums[middle] < nums[middle + 1]) {
                middle++;
            }
            while (middle - 1 < nums.length && nums[middle] < nums[middle - 1]) {
                middle--;
            }
            findAns = true;
            ans = middle;
        } else {
            if (middle != right) {
                findPeak(nums, left, middle);
            }

            if (middle != left) {
                findPeak(nums, middle, right);
            }

        }
    }

}
